package djistra;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author wanyuxiang
 * @version 1.0
 * @project Java_base
 * @create 2019-08-26 15:02
 **/
public class Graph {

    public Line line = new Line();

    /*
     * 顶点
     */
    private List<Vertex> vertexs;

    private List<Vertex> vertexsAns = new ArrayList<>();

    /*
     * 边
     */
    private int[][] edges;

    /*
     * 没有访问的顶点
     */
    private Queue<Vertex> unVisited;

    public Graph(List<Vertex> vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
        initUnVisited();
    }

    /*
     * 搜索各顶点最短路径
     */
    public void search() {
        while (!unVisited.isEmpty()) {
            Vertex vertex = unVisited.element();
            line.getResult().add(vertex);
            //顶点已经计算出最短路径，设置为"已访问"
            vertex.setMarked(true);
            //获取所有"未访问"的邻居
            List<Vertex> neighbors = getNeighbors(vertex);
            if (neighbors.size() > 0) {
                //更新邻居的最短路径
                Vertex nb = updatesDistance(vertex, neighbors);
                pop();
                unVisited.remove(nb);
                unVisited.add(nb);
            } else {
                pop();
            }
        }
        System.out.println("search over");
    }

    /*
     * 更新所有邻居的最短路径
     */
    private Vertex updatesDistance(Vertex vertex, List<Vertex> neighbors) {
        int res = Integer.MAX_VALUE;
        Vertex nb = null;
        for (Vertex neighbor : neighbors) {
            int distance = getDistance(vertex, neighbor);
            if (distance < res) {
                res = distance;
                if (nb != null) {
                    nb.setPath(Integer.MAX_VALUE);
                }
                nb = neighbor;
                nb.setPath(distance);
            }
        }
        line.setLineDistance(line.getLineDistance() + res);
        return nb;
    }

    public void printSSSP() {
        for (Vertex v : vertexsAns) {
            System.out.println(v.getName() + " " + v.getPath());
        }
        System.out.println(line.getLineDistance() + "->" + line.getResult());
    }

    /*
     * 初始化未访问顶点集合
     */
    private void initUnVisited() {
        unVisited = new PriorityQueue<>();
        unVisited.addAll(vertexs);
    }

    /*
     * 从未访问顶点集合中删除已找到最短路径的节点
     */
    private void pop() {
        vertexsAns.add(unVisited.poll());
    }

    /*
     * 获取顶点到目标顶点的距离
     */
    private int getDistance(Vertex source, Vertex destination) {
        int sourceIndex = vertexs.indexOf(source);
        int destIndex = vertexs.indexOf(destination);
        return edges[sourceIndex][destIndex];
    }

    /*
     * 获取顶点所有(未访问的)邻居
     */
    private List<Vertex> getNeighbors(Vertex v) {
        List<Vertex> neighbors = new ArrayList<>();
        int position = vertexs.indexOf(v);
        Vertex neighbor;
        int distance;
        for (int i = 0; i < vertexs.size(); i++) {
            if (i == position) {
                //顶点本身，跳过
                continue;
            }
            distance = edges[position][i];    //到所有顶点的距离
            if (distance < Integer.MAX_VALUE) {
                //是邻居(有路径可达)
                neighbor = getVertex(i);
                if (!neighbor.isMarked()) {
                    //如果邻居没有访问过，则加入list;
                    neighbors.add(neighbor);
                }
            }
        }
        return neighbors;
    }

    /*
     * 根据顶点位置获取顶点
     */
    private Vertex getVertex(int index) {
        return vertexs.get(index);
    }

    /*
     * 打印图
     */
    public void printGraph() {
        int verNums = vertexs.size();
        for (int row = 0; row < verNums; row++) {
            for (int col = 0; col < verNums; col++) {
                if (Integer.MAX_VALUE == edges[row][col]) {
                    System.out.print("X");
                    System.out.print(" ");
                    continue;
                }
                System.out.print(edges[row][col]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }

}
